package leetcode.f1t100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给一个数组, 找出所有3数相加等于0的组合
 * https://leetcode.com/problems/3sum/
 * @Author lichongxiao
 * @Date 2022/9/28 11:44
 */
public class Q15_3Sum {

    public static void main(String[] args) {
        List<List<Integer>> lists = new Q15_3Sum().threeSum(new int[]{-2,0,0,2,2});
        for(List<Integer> list : lists){
            for(Integer i : list){
                System.out.print(i);
            }
            System.out.println();
        }
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                break;
            }
            int left = i+1, right = nums.length-1;
            while(left < right) {
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else if(nums[i]+nums[left]+nums[right]<0){
                    left++;
                }else{
                    int leftNum = Integer.MIN_VALUE;
                    while (nums[i]+nums[left]+nums[right]==0 && left < right){
                        if(leftNum == nums[left]){
                            left++;
                            right--;
                            continue;
                        }
                        leftNum = nums[left];
                        List<Integer> result = new ArrayList<>();
                        result.add(nums[i]);
                        result.add(nums[left]);
                        result.add(nums[right]);
                        results.add(result);
                        left++;
                        right--;
                    }
                }
            }

            while(i+1<nums.length && nums[i] == nums[i+1]){
                i++;
            }

        }
        return results;
    }
}
